package com.caochenlei.linkedList;

/**
 * 单向链表实现代码
 */
public class SinglyLinkedList<E> {
    //定义结点类
    public class Node {
        E data;     //代表结点数据
        Node next;  //指向下个结点

        public Node(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{data=" + data + "}";
        }
    }

    private Node head;  //代表链表头部
    private Node last;  //代表链表尾部
    private int size;   //代表链表长度

    public SinglyLinkedList() {
        //头结点用于其他结点的连接，头结点的下标我们定义为-1
        this.head = new Node(null);
        //尾结点初始默认指向头结点，这样我们在添加的时候方便
        this.last = head;
        this.size = 0;
    }

    //获取链表当前大小
    public int size() {
        return size;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //检查下标是否合法
    public void checkIndex(int index) {
        if (index < 0 || (size - 1) < index) {
            throw new IndexOutOfBoundsException("链表下标越界异常，请检查链表的下标！");
        }
    }

    //连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) {
        if (prevNode != null) {
            prevNode.next = nextNode;
        }
    }

    //释放链表指定结点
    public void releaseNode(Node node) {
        if (node != null) {
            node.data = null;
            node.next = null;
        }
    }

    //返回链表最后结点
    public Node getLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表最后结点
        return last;
    }

    //返回链表首个结点
    public Node getFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表首个结点
        return head.next;
    }

    //获取指定位置结点
    public Node getIndex(int index) {
        //检查下标是否合法
        checkIndex(index);
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < (index + 1); i++) {
            curNode = curNode.next;
        }
        //返回指定位置结点
        return curNode;
    }

    //获取位置之前结点
    private Node getIndexPre(int index) {
        //检查下标是否合法
        checkIndex(index);
        //获取位置之前结点
        Node preNode = head;
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        //返回位置之前结点
        return preNode;
    }

    //链表尾后添加数据（需要考虑last指向问题）
    public void addLast(E e) {
        //获取旧的尾结点
        Node oldLast = last;
        //创建新的尾结点
        Node newLast = new Node(e);
        //旧新两结点连接
        connectNode(oldLast, newLast);
        //修改last指向
        last = newLast;
        //使链表长度加一
        size++;
    }

    //链表头后添加数据（不用考虑last指向问题）
    public void addFirst(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            addLast(e);
        } else {
            //获取首个结点
            Node firNode = head.next;
            //创建新的结点
            Node newNode = new Node(e);
            //三个结点连接
            connectNode(head, newNode);
            connectNode(newNode, firNode);
            //链表长度加一
            size++;
        }
    }

    //指定位置添加数据（不用考虑last指向问题）
    public void addIndex(int index, E e) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //创建一个新的结点
        Node newNode = new Node(e);
        //开始三个结点连接
        connectNode(preNode, newNode);
        connectNode(newNode, curNode);
        //当前链表长度加一
        size++;
    }

    //删除指定位置结点（需要考虑last指向问题）
    public void removeIndex(int index) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //获取位置之后结点
        Node nexNode = curNode.next;
        //修改last的指向
        if (curNode == last) {
            last = preNode;
        }
        //删除指定位置结点
        connectNode(preNode, nexNode);
        //释放链表指定结点
        releaseNode(curNode);
        //当前链表长度减一
        size--;
    }

    //删除链表首个结点（不用考虑last指向问题）
    public void removeFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //删除链表首个结点
        removeIndex(0);
    }

    //删除链表最后结点（不用考虑last指向问题）
    public void removeLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //删除链表最后结点
        removeIndex(size - 1);
    }

    //输出链表所有结点（不用考虑last指向问题）
    public void show() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点（除头结点）
        Node curNode = head.next;
        while (curNode != null) {
            System.out.println(curNode);
            curNode = curNode.next;
        }
    }

    //反转链表所有结点（需要考虑last指向问题）
    public void reverse() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //创建一个新头结点
        Node newHead = new Node(null);
        //获取链表的首结点
        Node oldFirst = head.next;
        //遍历链表所有结点（除头结点）
        Node newFirst;
        Node tmpNode;
        Node curNode = oldFirst;
        while (curNode != null) {
            //缓存当前结点下个结点
            tmpNode = curNode.next;
            //获取链表新头首个结点
            newFirst = newHead.next;
            //开始三个结点进行关联
            connectNode(newHead, curNode);
            connectNode(curNode, newFirst);
            //让当前的结点往后移动
            curNode = tmpNode;
        }
        //老头换新头首结点
        head.next = newHead.next;
        //修改last的指向
        last = oldFirst;
        //释放临时新头结点
        releaseNode(newHead);
    }

    //清空链表所有结点（需要考虑last指向问题）
    public void clear() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点（含头结点）
        Node tmpNode;
        Node curNode = head;
        while (curNode != null) {
            //缓存下个结点
            tmpNode = curNode.next;
            //释放当前结点
            releaseNode(curNode);
            //移动下个结点
            curNode = tmpNode;
        }
        //重置链表基本信息
        head = null;
        last = null;
        size = 0;
    }

    //顺序查找数据首次出现位置
    public int indexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //获取指定位置结点
        Node curNode = head;
        for (int i = -1; i < size; i++) {
            if (e.equals(curNode.data)) {
                return i;
            }
            curNode = curNode.next;
        }
        //没有找到返回负一
        return -1;
    }

    //逆序查找数据首次出现位置
    public int lastIndexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //反转当前链表结点
        reverse();
        //获取指定位置结点
        int index = indexOf(e);
        //反转当前链表结点
        reverse();
        //返回数据指定位置
        return index;
    }
}
